﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace FunnyFunction
{
    public class Cal100
    {
        /* 123456789 任意位置添加 + 或者 - ，使得结果为100
         * 顺序：
         * 0. 理论上最大的数字应该也只有3位，所以可以将数字进行拆分
         * 1. 先取1位，比如第一个1，则结果变成使得剩下的数字（23456789）成为 99 或者 -101
         * 2. 然后同样，再取1位，则结果变成使得剩下的数字（3456789）成为97或者-101
         * 3. 依次作为树结果来计算。
         */

        public bool Add = true;
        public int[] Arr;
        public int Num;
        public int need;
        public Cal100 parent = null;
        public void Start()
        {
            if (Arr==null || Arr.Length == 0)
                return;
            var n1 = Arr[0];
            this.Num = n1;
            var nArr = Arr.RemoveAt(0);
            if (nArr.Length == 0)
            {
                if (this.Num == this.need)
                    Print();
                else
                    return;
            }
            var a11 = new Cal100()
            {
                need = this.Add ? need - this.Num : need + this.Num,
                Arr = nArr,
                Add = true,
                parent = this
            };
            a11.Start();
            var a12 = new Cal100()
            {
                need = this.Num - need,
                Arr = nArr,
                Add = false,
                parent = this
            };
            a12.Start();

            if (Arr.Length >= 2)
            {
                var n2 = Arr[0] * 10 + Arr[1];
                this.Num = n2;
                var nArr2 = Arr.RemoveAt(0,2);
                if (nArr2.Length == 0)
                {
                    if (this.Num == this.need)
                        Print();
                    else
                        return;
                }
                var a21 = new Cal100()
                {
                    need = need - this.Num,
                    Arr = nArr2,
                    Add = true,
                    parent = this
                };
                a21.Start();
                var a22 = new Cal100()
                {
                    need = this.Num - need,
                    Arr = nArr2,
                    Add = false,
                    parent = this
                };
                a22.Start();
            }


            if (Arr.Length >= 3)
            {
                var n3 = Arr[0] * 100 + Arr[1] * 10 + Arr[2];
                this.Num = n3;
                var nArr3 = Arr.RemoveAt(0, 3);
                if (nArr3.Length == 0)
                {
                    if (this.Num == this.need)
                        Print();
                    else
                        return;
                }
                var a31 = new Cal100()
                {
                    need = need - this.Num,
                    Arr = nArr3,
                    Add = true,
                    parent = this
                };
                a31.Start();
                var a32 = new Cal100()
                {
                    need = this.Num - need,
                    Arr = nArr3,
                    Add = false,
                    parent = this
                };
                a32.Start();
            }
        }

        private void Print(List<string> list = null)
        {
            if (list == null)
                list = new List<string>();

            list.Insert(0, (Add ? " + " : " - ") + this.Num.ToString());

            if (parent != null)
            {
                parent.Print(list);
            }
            else
            {
                Console.Write("Find: ");
                foreach (var s in list)
                {
                    Console.Write(s);
                }
                Console.WriteLine("");
            } 
        }
    }

    public static class ArrExtend
    {
        public static int[] RemoveAt(this int[] Arr, int index, int length = 1)
        {
            var list = Arr.ToList();
            for (int i = 0; i < length; i++)
            {
                list.RemoveAt(index);
            }
            return list.ToArray();
        }
    }
}
